#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

bool a[10000], foi[10000];
int i, j, x, y, c, d, w, dd[4], ddd[4];


bool process(){
	queue<int> q;
	memset(foi,0,sizeof(foi));
	w=0;
	q.push(x);
	q.push(w);
	foi[x]=1;
	if(x==y)return 1;
	while(!q.empty()){
		c=q.front();q.pop();
		w=q.front();q.pop();
		w++;
		for(i=0;i<4;++i, c/=10){
			dd[i]=c%10;
		}
		for(i=0;i<4;++i){
			for(j=0;j<4;++j)ddd[j]=dd[j];
			if(i==3)j=1;
			else j=0;
			for(;j<10;++j){
				if(j==dd[i])continue;
				ddd[i]=j;
				d = ddd[0]+ddd[1]*10+ddd[2]*100+ddd[3]*1000;
				if((!foi[d])&&a[d]){
					if(d==y)return 1;
					foi[d]=1;
					//printf("%d %d\n",w,  d);
					q.push(d);
					q.push(w);
				}
			}
		}
	}
	
	return 0;
}
int main(){
	//freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
	memset(a,1,sizeof(a));
	a[0]=a[1]=0;
	for(i=2;i<10000;++i){
		if(a[i]){
			//printf("%d\n", i);
			for(j=i+i;j<10000;j+=i)a[j]=0;
		}
	}
	int t;
	scanf("%d", &t);
	while(t--){
		scanf("%d%d", &x, &y);
		if(process())printf("%d\n", w);
		else printf("Impossible\n");
	}
	return 0;
}
